package leetcode_core.leetcode_4;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年10月16日 10:02
 */
public class PossibleBipartition {
    private boolean ok = true;
    private boolean[] color;
    private boolean[] visited;
    //这道题的图需要我们自己来建
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[] graph = getGraph(n, dislikes);
        for(int i = 1;i<=n;i++){
            if(!visited[i]){
                dfs(graph,i);
            }
        }
        return ok;
    }
    private List<Integer>[] getGraph(int n,int[][] dislikes){
        List<Integer>[] graph = new LinkedList[n+1];
        //初始化图
        for(int i = 1;i<=n;i++){
            graph[i] = new LinkedList<>();
        }
        //证明有边
        for (int[] dislike : dislikes) {
            int person1 = dislike[0];
            int person2 = dislike[1];
            //person1和person2有边
            graph[person1].add(person2);
            graph[person2].add(person1);
        }
        return graph;
    }
    private void dfs(List<Integer>[] graph,int v){
        if(!ok){
            return ;
        }
        visited[v] = true;
        List<Integer> rel = graph[v];
        for (Integer point : rel) {
            if(!visited[point]){
                color[point] = !color[v];
                dfs(graph,point);
            }else{
                //检查
                if(color[point] == color[v]){
                    ok = false;
                    return;
                }
            }
        }
    }
}
